package com.zhao.utils;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.zhao.po.CarInfo;
import com.zhao.po.ItemInfo;

/**
 * 贪心算法－背包算法： 背包算法是从一堆里面选择出最多能容纳的。 我们要
 */
public class BackPackageUtil {

	private Float[] weights;// 物品重量

	private Float[] values;// 物品体积

	private CarInfo car;

	private List<ItemInfo> items;

	public BackPackageUtil(CarInfo car, List<ItemInfo> items) {
		super();

		this.car = car;
		this.items = items;
		int size = this.items.size();
		// 初始化属性的值
		this.weights = new Float[size];
		this.values = new Float[size];

		for (int i = 0; i < size; i++) {
			ItemInfo item = items.get(i);
			this.weights[i] = item.getItemweight();
			this.values[i] = item.getItemheight() * item.getItemlenght() * item.getItemwith();
		}
	}

	/**
	 * 根据物品重量和物品价值，求出每个物品的性价比－》将性价比进行排序－》选取性价比最高的物品添加到背包中－》直到背包不能再添加
	 */

	// 返回能装入车中的物品。 这里要实现的就是从items中取出不能装入的。
	public List<ItemInfo> backpack() {
		List<ItemInfo> backList = new ArrayList<ItemInfo>();
		// step1:求物品性价比－》并从大到小排序
		// 这里需要考虑怎么计算性价比
		int size = weights.length;// 物品数量
		Float[] prices = new Float[size];// 每个物品的性价比(每kg的价值)

		// 用一个数组用于保存排序后的性价比和最开始的物品重量的下标
		int[] tags = new int[size];
		for (int i = 0; i < size; i++) {
			prices[i] = (Float) values[i] / weights[i];
			tags[i] = i;// 默认排序
		}

		// 选择排序
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if (prices[i] < prices[j]) {
					// 交换
					Float temp = prices[i];
					prices[i] = prices[j];
					prices[j] = temp;

					int tag = tags[i];
					tags[i] = tags[j];
					tags[j] = tag;
				}
			}
		}

		Float capacity = car.getMaxweight();
		// 根据已经从大到小排好序的性价比，和相对应的重量和价值，添加到背包中
		for (int i = 0; i < size; i++) {
			// 根据tags数组中重量的下标，拿到重量
			if (weights[tags[i]] < capacity) {

				// 这里怎么将商品添加到新的集合? 怎么获取对应的item对象。 在这里我们能拿到的就是i
				ItemInfo item = this.items.get(i);

				// 这里还要加上一个判断： 判断这个商品是否能添加进车，这里需要做一个判断
				if (canFillItem(item)) {
					backList.add(item);
				}
				capacity = capacity - weights[tags[i]];
			}
		}

		return backList;
	}

	/**
	 * 判断这个商品能否装车
	 * 
	 * @return
	 */
	private Boolean canFillItem(ItemInfo item) {

		if (maxOfThree(item.getItemheight(), item.getItemlenght(), item.getItemwith()) < maxOfThree(
				this.car.getCarheight(), this.car.getCarlength(), this.car.getCarwith())) {
                 return true;
		}

		return false;
	}

	private Float maxOfThree(Float a, Float b, Float c) {
		Float max;
		if (a > b && a > c) {
			max = a;
		} else if (c > a && c > b) {
			max = c;
		} else {
			max = b;
		}
		return max;
	}

}
